package com.faiz.algorithm;

public class Backpack {

    /**
     * @param v 每个物品的价值
     * @param w 每个物品的重量
     * @param W 背包可承受的最大重量
     * @return
     */
    public static int backpack(int[] v, int[] w, int W) {
        int l = v.length;
        int[][] dp = new int[l + 1][W + 1];
        for (int j = 1; j <= W; j++) {
            for (int i = 1; i <= l; i++) {
                if (j >= w[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[l][W];
    }

    public static void main(String[] args) {
        int[] v = {1,2,3,4,5};
        int[] w = {1,2,3,4,5};
        System.out.println(backpack(v,w,15));
    }
}
